A Viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoders are used to decode a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in a telecommunication system. Such information can be transmitted through various media with each bit (or set of bits) representing a symbol instant. In the decoding process, the Viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which one bit sequence is most likely to have been transmitted. The possible transitions from a bit at one symbol instant, or state, to a bit at a next, subsequent, symbol instant or state is limited. Each possible transition from one state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can transition only to a limited number of next states upon receipt of the next bit in the bit stream. Thus, some paths survive and other paths do not survive during the decoding process. By eliminating those transitions that are not permissible, computational efficiency can be increased in determining the most likely paths to survive. The Viterbi decoder typically defines and calculates a branch metric associated with each branch and employs this branch metric to determine which paths survive and which paths do not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric, accumulated cost, that is updated at each symbol instant. For each possible transition, the path metric (i.e., accumulated cost) for the next state is calculated.
In a Viterbi decoder, the add-compare-select (ACS) module handles the addition of operands to evaluate different path metrics and the selection of one of the path metrics in accordance with the relative magnitudes of these metrics. More particularly, a path metric computation involves the addition of a branch metric with a previous value of a path metric. In this portion of the computation, multiple potential path metrics are calculated. For example, in 2-way ACS (also referred to as radix 2 ACS), values of two potential path metrics are calculated. A path metric computation also involves the selection of one path metric from two or more potential path metrics in accordance with their relative magnitudes. For example, in 2-way ACS, two potential path metrics are evaluated and the larger one is selected. In sum, ACS operations produce a result that is a path metric. The inputs to this operation are previously computed path metrics and relevant branch metrics.
However, as is known, existing ACS algorithms are sequential in nature. That is, the comparison of potential path metrics typically relies on the substantial completion of the add operations which generate those potential path metrics. Such a sequential arrangement disadvantageously impacts the speed performance of the overall ACS operation.
Thus, in Viterbi decoders, there is a need for techniques which improve the performance of ACS operations by overcoming the drawbacks inherent in the sequential handling of addition and comparison operations associated with conventional ACS schemes.